//--Built in system
#include "StdAfx.h"
#include "Graph.h"
//--
//--Using library read file
#include "iostream"
#include "fstream"
//--
using namespace std;
//--Function MatrixInit
void Graph::MatrixInit(int N,vector< vector<int> > &Array2D)
{
	Array2D.resize(N);
	int x = Array2D.size();
	for (int i = 0;i < x; i++)
	{
		Array2D[i].resize(N);
	}
}
void Graph::MatrixInit(int N,vector<int> &Array)
{
	Array.resize(N);
	int size = Array.size();
	for (int i = 0; i < size; i++)
	{
		Array[i] = -1;
	}
}
//--
//--Function GetData
void Graph::GetData(char *filename)
{	
	ifstream fin;
	fin.open(filename);
	fin >> N;
	MatrixInit(N,L);
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			fin >> L[i][j];
		}
	}
	fin >> s;
	fin >> t;
	fin.close();
}
//--
//--Function WriteData
void Graph::WriteData(char *filename)
{
	ofstream fin;
	fin.open(filename);
	fin << D[t];
	fin << "\n";
	int size_1 = Paths.size();
	for (int a = 0; a < size_1; a++)
	{
		int size_2 = Paths[a].size();
		for (int b = 0; b < size_2; b++)
		{
			fin << Paths[a][b];
			fin << " ";
		}
		fin << "\n";
	}
	fin.close();
}
//--
//--Function Check Peak t
int Graph::CheckPeak_t(int t, vector< vector<int> > V)
{
	int checked = 0;
	for (int i = 0; i < N; i++)
	{
		if(V[0][i] == t && V[1][t] != 0)
		{
			checked = 1;
			return checked;
		}
	}
	return checked;
}
//--
//--Function Choose Peak v
int Graph::ChoosePeak_v(vector<vector <int> >V)
{
	int peak = -1;
	int minimum = -1;
	for (int i = 0; i < N; i++)
	{
		if ((V[1][i] != 0) && ((minimum == -1 && (D[i] > minimum)) || (D[i] < minimum)))
		{
			minimum = D[i];
			peak = i;
		}
	}
	return peak;
}
//--
//--Function Advance Dijkstra Type 2
void Graph::Ad_Dijkstra_2()
{
	//--Step 1 :
	//--1.1.V = X
	vector<vector <int> >V(2, vector <int>(N,0));
	for (int i = 0; i < N; i++)
	{
		V[0][i] = i;
		V[1][i] = 1;
	}
	//--1.2.D[s] = 0
	MatrixInit(N,D);
	D[s] = 0;
	//--1.3.D[k] = MAXIMUM, with all k in X \ {s}
	for (int i = 0; i < N; i++)
	{
		if (D[i] != 0)
		{
			D[i] = MAXIMUM;
		}
	}
	//--1.4.Labels[k] = -1, with all k in X
	Labels2D.resize(N);
	for(int i= 0; i <N; i++)
	{
		Labels2D[i].push_back(-1);
	}
	//--
	//--Step 2 :
	//--2.1.While t in V
	while (CheckPeak_t(t,V) == 1)
	{
		//--2.2.Choose v in V with D[v] is minimum
		int v = ChoosePeak_v(V);
		if (v == -1)
		{
			break;
		}
		//--2.3.V = V \ {v}
		V[1][v] = 0;
		//--2.4.With all peaks k in V and connected from v to k
		for (int k = 0; k < N; k++)
		{
			if(L[v][k] > 0)
			{
				//--2.5.If D[k] > D[v] + Lvk
				if (D[k] > (D[v] + L[v][k]))
				{
					//--2.6.D[k] = D[v] + L[v][k]
					D[k] = D[v] + L[v][k];
					//--2.7.Labels[k] = v
					Labels2D[k][0]= v;
				}
				else if( D[k] == (D[v] + L[v][k]))
				{
					Labels2D[k].push_back(v);
				}
			}
		}
	}	
	//--
}
//--
//--Function SortPaths
void Graph::SortPaths()
{
	int rows_1 = Paths_temp.size();
	for (int a = 0; a < rows_1 - 1; a++)
	{
		for (int b = a + 1; b < rows_1; b++)
		{
			int size_1 = Paths_temp[a].size();
			int size_2 = Paths_temp[b].size();
			if (size_1 == size_2)
			{
				for (int c = 0; c < size_1; c++)
				{
					if (Paths_temp[a][c] > Paths_temp[b][c])
					{
						vector <int> temp;
						temp = Paths_temp[a];
						Paths_temp[a] = Paths_temp[b];
						Paths_temp[b] = temp;
					}
				}
			}
		}
	}
}
//--
//--Function OutScreen1
void Graph::OutScreen_1()
{
	int elements = 1;
	int rows = 0;
	int size = Labels2D[t].size();
	for (int i = 0; i < size; i++)
	{
		vector <int> start_peak;
		start_peak.push_back(t);
		int peak = Labels2D[t][i];
		start_peak.push_back(peak);
		OutScreen_2(start_peak,peak,elements,rows);
	}
	//--Run function SortPaths
	SortPaths();
	//--
	printf("%d\n",D[t]);
	//--Swap paths from low peak to high peak
	int size_2 = Paths_temp.size();
	Paths.resize(size_2);
	for (int a = 0; a < size_2; a++)
	{
		int b = Paths_temp[a].size()-1;
		Paths[a].resize(b + 1);
		int count = 0;
		for (b; b > -1; b--)
		{
			Paths[a][count] = Paths_temp[a][b];
			printf("%d ", Paths[a][count]);
			count = count + 1;
		}
		printf("\n");
	}
}
//--
//--Function OutScreen2
void Graph::OutScreen_2(vector<int> &start_peak, int peak, int &elements,int &rows)
{
	vector <int> temp = start_peak;
	int rows_2 = Labels2D[peak].size();
	for (int i = 0; i < rows_2; i++)
	{
		int peak_2 = Labels2D[peak][i];
		if (peak_2 == -1)
		{
			Paths_temp.resize(elements);
			int rows_3 = temp.size();
			Paths_temp[rows].resize(rows_3);
			int size = temp.size();
			for (int j = 0; j < size; j++)
			{
				int peak_3 = temp[j];
				Paths_temp[rows][j] = peak_3;
			}
			elements = elements + 1;
			rows = rows + 1;
			return;
		}
		start_peak.push_back(peak_2);
		OutScreen_2(start_peak,peak_2,elements,rows);
		start_peak = temp;
	}
}